package cn.sort;

public class MergeSortSum {
    public static int mergeSortSum(int[] arr){
        if(null == arr || arr.length < 2){
            return 0;
        }
        // 排序并返回最小和
        return mergeSortSumTest(arr,0,arr.length-1);

    }

    public static int mergeSortSumTest(int[] arr, int L, int R) {
        if(L == R ) {
            return 0;
        }
        int mid = L + (R -L) /2;
        // 左边的最小和+右边的最小和+最后排序好的最小和就是最后的结果
        return mergeSortSumTest(arr, L, mid) + mergeSortSumTest(arr, mid+1, R) + mergeSortSumArray(arr,L,mid,R);
    }

    public static int mergeSortSumArray(int[] arr, int l, int mid, int r) {
        int[] arrs = new int[r-l+1];
        int i = 0;
        int p1 = l;
        int p2 = mid + 1;
        int sum = 0;// 最小和

        while(p1 <= mid && p2 <= r){
            // 如果左边小于右边，那就有(r - p2 + 1)个arr[p1]元素的和是最小和
            // 如果大于右边，返回0
            sum += arr[p1] < arr[p2]?(r - p2 + 1)*arr[p1]:0;
          // sum += arr[p1] > arr[p2]?(mid - p1 + 1):0; //求逆序对
            arrs[i++] = arr[p1] < arr[p2]?arr[p1++]:arr[p2++];
        }

        while(p1<=mid){
            arrs[i++] = arr[p1++];
        }

        while(p2<=r){
            arrs[i++] = arr[p2++];
        }
        for (int j = 0; j < arrs.length; j++) {
            arr[l+j] = arrs[j];
        }
        return sum;
    }

    public static void main(String[] args) {
        //int[] arr = {1,2,3,4,-1,9};
        int[] arr = {6,1,2,3,4,5};
        int i = mergeSortSum(arr);
        System.out.println(i);
    }
}
